package 剑指offer;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Random;

public class Offer39_JZ28 {
    // hashmap方法
    public static int MoreThanHalfNum_Solution(int [] array) {
        int count = 1;
        int num = array[0];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<array.length; i++) {
            map.put(array[i], map.getOrDefault(array[i], 0)+1);
            if (map.get(array[i]) > count) {
                count = map.get(array[i]);
                num = array[i];
            }
        }
        return num;
    }

    //快排法
    public static int MoreThanHalfNum_Solution2(int[] array) {
        int middle = array.length/2;
        int start = 0;
        int end = array.length-1;
        int index = partition(array, start, end);
        while (index != middle) {
            if (index > middle) {
                end = index - 1;
                index = partition(array, start, end);
            } else {
                start = index + 1;
                index = partition(array, start, end);
            }
        }
        int result = array[middle];
        return result;
    }


    public static void main(String[] args) {
        int[] arr = {47,47,72,47,72,47,79,47,12,92,13,47,47,83,33,15,18,47,47,47,47,64,47,65,47,47,47,47,70,47,47,55,47,15,60,47,47,47,47,47,46,30,58,59,47,47,47,47,47,90,64,37,20,47,100,84,47,47,47,47,47,89,47,36,47,60,47,18,47,34,47,47,47,47,47,22,47,54,30,11,47,47,86,47,55,40,49,34,19,67,16,47,36,47,41,19,80,47,47,27};
        System.out.println(MoreThanHalfNum_Solution2(arr));
//        quickSort(arr,  0, arr.length-1);
//        System.out.println(Arrays.toString(arr));
    }


    // 快速排序
    public static void quickSort(int[] data, int start, int end) {
        if (start < end) {
            int index = partition(data, start, end);
            if (index > start) {
                quickSort(data, start, index-1);
            }
            if (index < end) {
                quickSort(data, index+1, end);
            }
        }
    }

    public static int partition(int[] data, int start, int end) {
        int pivot = data[start];
        while (start < end) {
            while (start<end && data[end]>=pivot) {
                end--;
            }
            data[start] = data[end];
            while (start<end && data[start]<=pivot) {
                start++;
            }
            data[end] = data[start];
        }
        data[start] = pivot;
        return start;
    }

    public static void swap(int[] data, int index, int end) {
        int temp = data[index];
        data[index] = data[end];
        data[end] = temp;
    }
}
